
#include <iostream>
#include <string>
#include <vector>
#include <list>
using namespace std;

struct ListNode 
{
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
 
class Solution
{
public:
    ListNode* addInList(ListNode* head1, ListNode* head2)
    {
        if (!head1)
            return head2;
        if (!head2)
            return head1;

        list<int> l1, l2;
        for (ListNode* cur1 = head1, *cur2 = head2; cur1 || cur2;)
        {
            if (cur1)
            {
                l1.push_back(cur1->val);
                cur1 = cur1->next;
            }
            if (cur2)
            {
                l2.push_back(cur2->val);
                cur2 = cur2->next;
            }
        }

        int carry = 0;
        ListNode* prev = nullptr;
        for (auto it1 = l1.rbegin(), it2 = l2.rbegin(); it1 != l1.rend() || it2 != l2.rend() || carry;)
        {
            int a = it1 == l1.rend() ? 0 : *it1;
            int b = it2 == l2.rend() ? 0 : *it2;

            ListNode* node = new ListNode((a + b + carry) % 10);
            node->next = prev;
            prev = node;

            carry = (a + b + carry) / 10;
            if (it1 != l1.rend())
                ++it1;
            if (it2 != l2.rend())
                ++it2;
        }

        return prev;
    }

    string solve(string s, string t)
    {
        if ("0" == s || "0" == t)
            return "0";

        int ns = s.size(), nt = t.size();
        vector<int> v(ns + nt);

        reverse(s.begin(), s.end());
        reverse(t.begin(), t.end());
        for (int i = 0; i < ns; ++i)
        {
            for (int j = 0; j < nt; ++j)
            {
                v[i + j] += (s[i] - '0') * (t[j] - '0');
                if (v[i + j] > 9)
                {
                    v[i + j + 1] += v[i + j] / 10;
                    v[i + j] %= 10;
                }
            }
        }

        string res;
        for (int i = v.size() - 1; i >= 0; --i)
        {
            if (v[i])
            {
                while (i >= 0)
                {
                    res += to_string(v[i--]);
                }
            }
        }

        return res;
    }

    string solve1(string s, string t)
    {
        if ("0" == s)
            return t;
        if ("0" == t)
            return s;

        int ns = s.size(), nt = t.size();
        vector<int> v(ns + nt);

        for (int i = ns - 1, j = nt - 1, idx = 0; i >= 0 || j >= 0; --i, --j, ++idx)
        {
            int a = i >= 0 ? s[i] - '0' : 0;
            int b = j >= 0 ? t[j] - '0' : 0;
            cout << a << " " << b << endl;
            v[idx] += a + b;
            if (v[idx] > 9)
            {
                v[idx + 1] += v[idx] / 10;
                v[idx] %= 10;
            }
        }

        string res("0");
        for (int i = v.size() - 1; i >= 0; --i)
        {
            if (v[i])
            {
                res.clear();
                while (i >= 0)
                {
                    res += to_string(v[i--]);
                }
            }
        }

        return res;
    }

    string solve2(string s, string t)
    {
        string res;
        int ns = s.size(), nt = t.size();

        int carry = 0;
        for (int i = ns - 1, j = nt - 1; i >= 0 || j >= 0 || carry; --i, --j)
        {
            int a = i >= 0 ? s[i] - '0' : 0;
            int b = j >= 0 ? t[j] - '0' : 0;

            res += (a + b + carry) % 10 + '0';
            carry = (a + b + carry) / 10;
        }
        reverse(res.begin(), res.end());

        return res;
    }
};

ListNode* Create1()
{
    ListNode* node9 = new ListNode(9);
    ListNode* node3 = new ListNode(3);
    ListNode* node7 = new ListNode(7);
    node9->next = node3;
    node3->next = node7;

    return node9;
}

ListNode* Create2()
{
    ListNode* node6 = new ListNode(6);
    ListNode* node3 = new ListNode(3);
    node6->next = node3;

    return node6;
}

void Test1()
{
    ListNode* l1 = Create1();
    ListNode* l2 = Create2();
    Solution().addInList(l1, l2);
}

void Test2()
{
    string s = "1";
    string t = "99";
    Solution().solve1(s, t);
}

int main()
{
    Test1();
    Test2();

	return 0;
}